package com.zk.algorithm.dynamicprogramming;

import com.zk.algorithm.annotation.CrackingTheCodingInterview6;
import com.zk.algorithm.bean.Point;

import java.util.ArrayList;
import java.util.HashSet;

/**
 * 8.2 机器人从左上角走到 --> 右下角 (right, down)
 *
 * @author zk
 */
@CrackingTheCodingInterview6("8.2")
public class RobotInAGrid {

    // (r-1, c) => (r, c)
    // (r, c-1) => (r, c)
    //
    // 别用 x, y 代表坐标，因为实际上应该是 matrix[y][x]
    //
    // 没有 failedPoints，则复杂度：O(2^(r+c))
    // 有 failedPoints: 则复杂度 O(rc)
    public ArrayList<Point> getPath(boolean[][] maze) {
        if (maze == null || maze.length == 0) {
            return null;
        }

        // [0,0,0,0,0]
        // [0,1,0,0,0]
        // [0,0,1,0,0]
        //
        // row: maze.length
        // col: maze[0].length
        ArrayList<Point> path = new ArrayList<>();
        // 避免重复计算
        HashSet<Point> failedPoints = new HashSet<Point>();
        if (getPath(maze, maze.length - 1, maze[0].length - 1, path, failedPoints)) {
            return path;
        }

        return null;
    }

    private boolean getPath(boolean[][] maze, int row, int col, ArrayList<Point> path, HashSet<Point> failedPoints) {
        if (col < 0 || row < 0 || !maze[row][col]) {
            return false;
        }

        Point point = new Point(row, col);
        if (failedPoints.contains(point)) {
            return false;
        }

        boolean isAtOrigin = (row == 0) && (col == 0);

        if (isAtOrigin ||
                getPath(maze, row, col - 1, path, failedPoints) ||
                getPath(maze, row - 1, col, path, failedPoints)) {
            path.add(point);
            return true;
        }

        failedPoints.add(point);
        return false;
    }

}
